package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class NextPermutation {

  /*
   * 搞个例子模拟，比如[1,2,4,6,5,3]，这个排列的下一个排列是[1,2,5,3,4,6]。
   * 我们研究下这个排列[1,2,4,6,5,3]
   * 要想找到它的下一个排列，那么我们应该从后往前看：
   * 先从后往前遍历，找到打破升序排列的那个数，这里即为[4]这个元素，因为[6,5,3]从后往前都是升序排序。将[4]这个元素下标记为idx；
   * 再次从后往前遍历，找到大于[4]的元素，这里即为[5]这个元素，将[5]这个元素下标记为idx2；
   * 将nums[idx]和nums[idx2]交换，那么排列变成了[1,2,5,6,4,3]；
   * 交换完后，[6,4,3]依然是降序排列的，我们需要将其改为升序，即反转一下，变成排列[1,2,5,3,4,6]，为答案。
   * 注意：
   * 当idx找不到时，即整个排列是降序的（从后往前是升序），那么直接反转，得到升序的一个排列，即答案
   * 
   * 作者：yusir
   * 链接：https://leetcode.cn/problems/next-permutation/solutions/3602232/gao-ge-li-zi-mo-ni-yi-xia-pythonjavacti-q4gld/
   * 来源：力扣（LeetCode）
   * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
   * 。
   */

  // leetcode submit region begin(Prohibit modification and deletion)
  class Solution {

    // 有点子蓝，多刷几次
    public void nextPermutation(int[] nums) {

      if (nums == null || nums.length <= 1) {
        return;
      }

      int idx = -1;
      // 从后往前找，找到第一个 从右看，打破 升序规则的人
      for (int i = nums.length - 2; i >= 0; i--) {
        if (nums[i] < nums[i + 1]) {
          idx = i;
          break;
        }
      }

      // 如果找不到 ，说明整个数组都是逆序的，直接反转即可
      if (idx == -1) {
        reverse(nums, 0, nums.length - 1);
        return;
      }

      // 再次从后往前找，找到第一个 大于 nums[idx] 的元素 ，记为 idx2



      int idx2 = -1;
      for (int i = nums.length - 1; i > idx; i--){
        if(nums[i]>nums[idx]){
          idx2 = i;
          break;
        }
      }


      // 交换 idx 和 idx2
      int tmp = nums[idx];
      nums[idx] = nums[idx2];
      nums[idx2] = tmp;


      // 反转 idx2 之后元素
      reverse(nums, idx + 1, nums.length - 1);









    }

    void reverse(int[] nums, int start, int end) {
      while (start < end) {
        int tmp = nums[start];
        nums[start] = nums[end];
        nums[end] = tmp;
        start++;
        end--;

      }
    }

    // leetcode submit region end(Prohibit modification and deletion)

  }

}
